package ScanLineAlghorithms.RectanglesUnion;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Stack;

import DataModel.LayoutManager.CEdge;
import DataModel.LayoutManager.CRectangle;
import DataModel.SegmentTree.SegmentTree;

import ScanLineAlghorithms.ScanLineFunctions;

/**
 * Implementation of rectangles union algorithm
 * Reference: Schamos and Preparata: Introduction to Alghorithms, Chapter 8 -Geometry of rectangles.
 * @author Guy
 *
 */
public class RectanglesUnion {
	
	/**
	 * Impementation of calculates union of given set of rectangles.
	 * Direction of perimeter is such that when walking from edge start to its end , 
	 * the enclosed union is on the right side
	 * @param recsList input rectangles to unite
	 * @return all edges of the union in order
	 */ 
	
	@SuppressWarnings("unchecked")
	public static LinkedList<CEdge> Activate(LinkedList<CRectangle> recsList)
	{	
		
		LinkedList<CEdge> verticalEdges = new LinkedList<CEdge>();
		LinkedList<CEdge> horizontalEdges = new LinkedList<CEdge>();
		Hashtable<CEdge,CEdge> linkage = new Hashtable<CEdge, CEdge>();
		//Hash between x endpoint and vertical edges at this point
		Hashtable<Long, LinkedList<CEdge>> xScale = ScanLineFunctions.initEndpoints(recsList , 'x');
		
		//vertical edges of rectangles
		ArrayList<CEdge> yEdges = ScanLineFunctions.extractEdges(recsList, 'y');
		//initialize empty segment tree
		SegmentTree statusTree = new SegmentTreeUnionAlg(yEdges,'y');
				
		//x scale rectangles enpoints on wich we iterate
		LinkedList keys = new LinkedList(xScale.keySet());
		Collections.sort(keys);
		
		ListIterator itKeys  = keys.listIterator();
		
		while (itKeys.hasNext()) {
			Long key = (Long)itKeys.next();
			//extracting vertical edges at point
			LinkedList<CEdge> edges = xScale.get(key);
			ListIterator itEdges = edges.listIterator();
		
			//Stack of endpoints of vertical edges at current position
			while (itEdges.hasNext()) {
				boolean invert = false;
				Stack curVerEndPoints = null;
				CEdge edge = (CEdge) itEdges.next();
				//right side of rectangle
				if (edge.getEndPoint().y<=edge.getStartPoint().y) {
					invert = true;
					statusTree.remove(edge);
					curVerEndPoints = Contribute.activate(edge.getStartPoint().y,edge.getEndPoint().y,statusTree.getRoot());
				}
				//left side of rectangle
				if (edge.getStartPoint().y<=edge.getEndPoint().y) {
					curVerEndPoints = Contribute.activate(edge.getStartPoint().y,edge.getEndPoint().y,statusTree.getRoot());
					statusTree.insert(edge);
					
				}
				createVerEdges(verticalEdges,curVerEndPoints,invert,key);
			}
			
		}
		calcHorizontalEdges(verticalEdges, horizontalEdges, linkage);
		return createUnion(verticalEdges, horizontalEdges, linkage);
	}
	
	//Calculating horizontal edges

	@SuppressWarnings("unchecked")
	private static void calcHorizontalEdges(LinkedList<CEdge> edges,LinkedList<CEdge> horizontalEdges ,Hashtable<CEdge,CEdge> linkage) {
		ListIterator it = edges.listIterator();
		LinkedList<Triple> triples = new LinkedList<Triple>();
		while (it.hasNext()) {
			CEdge e = (CEdge) it.next();
			Triple t1 = new Triple(e.getStartPoint().x,e.getStartPoint().y,e.getEndPoint().y,e);
			Triple t2 = new Triple(e.getStartPoint().x,e.getEndPoint().y,e.getStartPoint().y,e);
			triples.add(t1);
			triples.add(t2);
		}
		Collections.sort(triples);
		//		To remove printout
		//Triple.ptintTriples(triples);
		it = triples.listIterator();
		while (it.hasNext()) {
			Triple t1 = (Triple) it.next();
			Triple t2 = (Triple) it.next();
			
			CEdge hrzEdge = calculateHorizontaleEdge(t1,t2,linkage);
			horizontalEdges.add(hrzEdge);
		}
	}
	
	private static CEdge calculateHorizontaleEdge(Triple t1, Triple t2, Hashtable<CEdge,CEdge> linkage) {
		CEdge owner1 = t1.owner;
		CEdge owner;
		CEdge e;
		CEdge pred;
		if (t1.b!=t2.b) {
			System.err.println("Error in Generating horizontal Edges");
			return null;
		}
		//Horizontal edge is directed from left to right if correspoinding edge of point 1 is directed downward and y<y1(See Schamos and Preparata: Introduction to Alghorithms, page 342)
		if ((owner1.getEndPoint().y<=owner1.getStartPoint().y&& t1.b<=t1.t) || (owner1.getEndPoint().y>=owner1.getStartPoint().y && t1.b>=t1.t)) {
			e =  new CEdge((int)t1.x,(int)t1.b,(int)t2.x,(int)t2.b,-1, null);
			owner = t2.owner;
			pred  = t1.owner;
		} else { 
			e = new CEdge((int)t2.x,(int)t2.b,(int)t1.x,(int)t1.b,-1, null);
			owner = t1.owner;
			pred  = t2.owner;
		
		}
		
			
		linkage.put(pred, e);
		
		linkage.put(e, owner);
		
		return e;
	}
	

	private static void createVerEdges(LinkedList<CEdge> edges, Stack<Long> curVerEndPoints, boolean invert ,Long xCoord) {
		
		while (!curVerEndPoints.isEmpty()) {
			Long begin = null;
			Long end = null;
			if (invert) {
			    begin = curVerEndPoints.pop();
				end = curVerEndPoints.pop();
			} else {
				end = curVerEndPoints.pop();
				begin = curVerEndPoints.pop();
			}
			// evgeni added the *.intValue() stuff
			CEdge e = new CEdge(xCoord.intValue(), begin.intValue(), xCoord.intValue(), end.intValue(), -1, null);
			edges.add(e);
			
		}
	
	}
	private static LinkedList<CEdge> createUnion(LinkedList<CEdge> verticalEdges, LinkedList<CEdge> horizontalEdges, Hashtable<CEdge,CEdge> linkage) {
		LinkedList<CEdge> union = new LinkedList<CEdge>();
		while (!verticalEdges.isEmpty()) {
			CEdge first = verticalEdges.getFirst();
			CEdge curEdge = first;
			do {
				verticalEdges.remove(curEdge);
				union.add(curEdge);
				curEdge = linkage.get(curEdge);
			} while (curEdge != first) ;
		}
		return union;
	}
}